دانشگاه فردوسی مشهد

دانشکده مهندسی- گروه کامپیوتر

پایان‌نامه کارشناسی ارشد

تلفیق الگوریتم رقابت استعماری و انتخاب سریع زمان آماده­سازی در حل مسأله برنامه­ریزی توالی هواپیماها

(Combination of Imperialist Competitive Algorithm with Earliest Ready Time for Aircraft Sequencing Problem)

استاد راهنما:
دکتر رضا منصفی

برای رعایت حریم خصوصی نام نگارنده درج نمی شود

تکه هایی از متن به عنوان نمونه :

چکیده

مدیریت ترافیک هوایی یکی از مشاغل حساس و پراسترس است که همه‌روزه با مشکلات و موانع مختلفی روبه­رو می­شود و مسأله توالی هواپیما (Aircraft Sequencing Problem) یکی از مهم­ترین مسائلی است که این روزها در حوزه کاری مراقبت پرواز (Air Traffic Control) به آن پرداخته می­شود.

مسأله توالی هواپیما یک مسأله NP-سخت است، الگوریتم­های دقیق کارایی خود را بر روی این مسأله در ابعاد بالا از دست می­دهند و نمی­توانند به جواب بهینه در یک‌زمان قابل‌قبول دست یابند؛ درنتیجه امروزه برای حل این­گونه مسائل از الگوریتم­های ابتکاری و فرا ابتکاری استفاده می­شود.

در این پایان‌نامه سعی شده با تلفیق الگوریتم ERT(Earliest Ready Time) جهت انتخاب بهترین هواپیمای آماده عملیات با الگوریتم استعماری اصلاحی که از روش نزدیک­ترین همسایه تصادفی برای تابع جذب در کنار روش بهبود­دهنده سه­نقطه­ای برای تابع انقلاب استفاده کرده، روش جدیدی در حل مسأله توالی هواپیما ارائه شود. نتایج حاصل از پیاده‌سازی این الگوریتم نشان می­دهد که در مقایسه با سایر الگوریتم­ها از کارایی بالایی برخوردار است.

کلمات کلیدی: توالی فرود هواپیماها، الگوریتم رقابت استعماری اصلاحی، مدیریت ترافیک هوایی، الگوریتم انتخاب سریع زمان آماده­سازی

فهرست مطالب

1- مقدمه طرح پیشنهادی………………………………………………………………………………………………………………. 1

1-1- مقدمه…………………………………………………………………………………………………………………………………… 2

1-2- طرح موضوع…………………………………………………………………………………………………………………………… 4

1-3- مفروضات، محدودیت­ها……………………………………………………………………………………………………………. 6

1-4- اهداف تحقیق…………………………………………………………………………………………………………………………. 8

1-5- جنبه­ی جدید بودن و نوآوری………………………………………………………………………………………………….. 9

1-6- نتایج حاصل از تحقیق…………………………………………………………………………………………………………….. 9

1-7- ساختار پایان­نامه…………………………………………………………………………………………………………………. 10

2- مروری بر کارهای گذشته………………………………………………………………………………………………………. 11

2-1- مقدمه………………………………………………………………………………………………………………………………… 12

2-2- توالی فرود هواپیما………………………………………………………………………………………………………………. 12

2-3- تخصیص ورودی مسافری…………………………………………………………………………………………………….. 15

2-4- پیشینه تحقیق……………………………………………………………………………………………………………………. 17

2-5- مدل برنامه­ریزی خطی برنامه………………………………………………………………………………………………. 21

3- روش پیشنهادی…………………………………………………………………………………………………………………… 25

3-1- راه­کار پیشنهادی…………………………………………………………………………………………………………………. 26

3-2- الگوریتم تکاملی………………………………………………………………………………………………………………….. 26

3-2-1- مقدمه…………………………………………………………………………………………………………………………….. 26

3-2-2- علت استفاده از الگوریتم‌های تکاملی………………………………………………………………………………… 29

3-2-3- انواع الگوریتم‌های تکاملی………………………………………………………………………………………………… 29

3-3- الگوریتم رقابت استعماری……………………………………………………………………………………………………. 32

3-3-1- شکل­دهی امپراطوری اولیه……………………………………………………………………………………………….. 34

3-3-2- مدل‌سازی سیاست جذب……………………………………………………………………………………………….. 38

3-3-3- جابجایی موقعیت مستعمره و امپرالیسست……………………………………………………………………….. 41

3-3-4- قدرت کل یک امپراطوری………………………………………………………………………………………………… 42

3-3-5- رقابت استعماری…………………………………………………………………………………………………………….. 43

3-3-6- سقوط امپراطوری­های ضعیف……………………………………………………………………………………………. 46

3-3-7- همگرایی………………………………………………………………………………………………………………………… 46

3-4- الگوریتم رقابت استعماری اصلاحی………………………………………………………………………………………. 48

3-5- الگوریتم‌های ترکیبی بکار رفته…………………………………………………………………………………………….. 51

4- ارزیابی سیستم……………………………………………………………………………………………………………………. 53

4-1- مقدمه………………………………………………………………………………………………………………………………… 54

4-2- مدل‌سازی روش پیشنهادی…………………………………………………………………………………………………. 55

4-3- ارزیابی راه­کار پیشنهادی………………………………………………………………………………………………………. 56

4-4- مسائل مورد مقایسه…………………………………………………………………………………………………………….. 59

4-4-1- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 15………………………………………………………. 59

4-4-2- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 20………………………………………………………. 61

4-4-3- مقایسه نتایج پروازهای ورودی و خروجی به تعداد 25………………………………………………………. 62

5- نتیجه­گیری و ارائه پیشنهاد‌ها…………………………………………………………………………………………….. 64

5-1- جنبه نوآوری……………………………………………………………………………………………………………………….. 65

5-2- نتیجه مقایسه نتایج…………………………………………………………………………………………………………….. 65

5-3- پیشنهاد‌ها…………………………………………………………………………………………………………………………… 66

6- مراجع……………………………………………………………………………………………………………………………………. 67

فهرست جدول‌ها و شکل‌ها

شکل 1-1- حل مسأله ASP به روش FCFS…………………………………………………………….. 5

شکل 2-1- فاصله ایمنی بین دو سر بال…………………………………………………………………………………………. 23

شکل 3-1- طرح کلی الگوریتم تکاملی…………………………………………………………………………………………… 28

شکل 3-2- فلوچارت الگوریتم ICA………………………………………………………………………………………………. 33

شکل 3-3- اجزای اجتماعی و سیاسی تشکیل‌دهنده کشور……………………………………………………………… 35

شکل 3-4- چگونگی شکل­گیری امپراطوری­های اولیه……………………………………………………………………… 38

شکل 3-5- شمای کلی حرکت مستعمرات به سمت امپریالیست…………………………………………………….. 39

شکل 3-6- حرکت واقعی مستعمرات به سمت امپریالیست……………………………………………………………… 40

شکل 3-7- تغییر جای استعمارگر و مستعمره………………………………………………………………………………… 42

شکل 3-8- کل امپراطوری پس از تغییر موقعیت……………………………………………………………………………… 42

شکل 3-9- شمای کلی رقابت استعماری……………………………………………………………………………………….. 43

شکل 3-10-سقوط امپراطوری ضعیف…………………………………………………………………………………………….. 47

شکل 3-11- گراف همسایگی با پنج گره……………………………………………………………………………………….. 49

شکل 3-12- بهبوددهنده سه‌نقطه‌ای……………………………………………………………………………………………… 50

شکل 3-13- فلوچارت راه­کار پیشنهادی…………………………………………………………………………………………. 52

جدول 1-1- حداقل زمان فاصله………………………………………………………………………………………………………… 6

جدول 4-1 نتایج مربوط به الگوریتم ERT و AATCSR برای 15 نمونه…………………….. 59

جدول 4-2 نتایج مربوط به الگوریتم ICA برای 15 نمونه…………………………….. 60

جدول 4-3 نتایج مربوط به الگوریتم ترکیبی MICA و ERT برای 15 نمونه……………….. 60

جدول 4-4 مقایسه نتایج مربوط به 15 پرواز…………………………………………………………………………. 60

جدول 4-5 نتایج مربوط به الگوریتم ERT و AATCSR برای 20 نمونه…………………….. 61

جدول 4-6 نتایج مربوط به الگوریتم ICA برای 20 نمونه…………………………….. 61

جدول 4-7 نتایج مربوط به الگوریتم ترکیبی MICA و ERT برای 20 نمونه……………….. 61

جدول 4-8 مقایسه نتایج مربوط به 20 پرواز…………………………………………………………………………. 62

جدول 4-9 نتایج مربوط به الگوریتم ERT و AATCSR برای 25 نمونه…………………….. 62

جدول 4-10 نتایج مربوط به الگوریتم ICA برای 25 نمونه…………………………… 62

جدول 4-11 نتایج مربوط به الگوریتم ترکیبی MICA و ERT برای 25 نمونه…………….. 63

جدول 4-12 مقایسه نتایج مربوط به 25 پرواز………………………………………………………………………. 63

1-1- مقدمه

یکی از موضوعات موردتوجه در صنعت هوانوردی، مبحث برنامه­ریزی فرود هواپیماهای ورودی به فرودگاه است. با ورود هواپیماهای مختلف به محدوده­ی راداری فرودگاه، مراقبین پرواز در برج مراقبت باید ترتیب فرود هواپیماهایی که در آن لحظه در آسمان فرودگاه در حال پرواز هستند را مشخص نمایند. برای اختصاص چنین ترتیب فرودی محدودیت­های مختلفی موردتوجه قرار­می­گیرد که از آن جمله می‌توان به محدودیت جداسازی دو هواپیما اشاره نمود. این محدودیت از دیدگاه مباحث آئرودینامیک اهمیت زیادی دارد و در صورت عدم رعایت آن امکان بروز حادثه برای هواپیماهای متوالی وجود دارد.

مهم­ترین نتیجه­ی موردنظر برنامه­ریزی فرود هواپیماها، کمینه کردن تأخیرها است که از ایجاد هزینه­ی سوخت اضافه برای هواپیماها و همین‌طور ایجاد نارضایتی مسافران جلوگیری می‌کند. ازآنجایی‌که هزینه­های مربوط به سوخت ناوگان پروازی درصد قابل‌توجهی از هزینه­های شرکت‌های هواپیمایی را شامل می­شود، برنامه­ریزی فرود هواپیماها موردتوجه شرکت‌های هواپیمایی و همچنین شرکت‌های فرودگاهی قرارگرفته است. همین امر باعث شده است که اغلب فرودگاه­هایی که عملکرد بهتری در خصوص مدیریت ترافیک پروازی دارند، توجه شرکت‌های هواپیمایی بیشتری را به خود جلب کنند. از سوی دیگر، در صورت دستیابی به عملکردی مناسب در مدیریت ترافیک پروازها، شرکت‌های فرودگاهی این امکان را خواهند داشت که در بازه زمانی ثابت، پذیرای تعداد بیشتری از هواپیما باشند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 709